#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        //状态表示 dp[i] 第i天结束后的最大利润
        //[0]有股票[1]无股票|[k]交易次数
        vector<vector<vector<int>>>dp(prices.size(),vector<vector<int>>(2,vector<int>(k+1,0)));
        for(int i=0;i<k;i++) dp[0][0][i]=prices[0]*-1;
        for(int i=1;i<dp.size();i++){
            //k次的是否持有股票的转化转换
            for(int j=0;j<k;j++){
                dp[i][0][j]=max(dp[i-1][0][j],dp[i-1][1][j]-prices[i]);
                dp[i][1][j+1]=max(dp[i-1][1][j+1],dp[i-1][0][j]+prices[i]);
            }
        }
        return *max_element(dp.back()[1].begin(),dp.back()[1].end());
    }
};